package pro1_10.pro5;

/**
 5.查找最小的k个元素（数组）
 题目：输入n个整数，输出其中最小的k个。
 例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

 思路 依然使用快速排序 但是不需要全部排 只需要快速排序中基数比k大的就行了  减少不必要的排序
 */
public class Main2 {

    public static void main(String[] args) {
        int[] a = {12,35,2,1,3,4,51,2,39,9,7,7};
        for(int i : a){
            System.out.print(i + " ");
        }
        System.out.println();
        int k = 2;
        partQuickSort(a,0,a.length-1,k);
        for(int i : a){
            System.out.print(i + " ");
        }
    }

    public static void partQuickSort(int[] a, int begin, int end, int k){
        if(begin < end){
            int x = a[begin];
            int i = begin;
            int j = end;
            while(i < j) {
                while (i < j && a[j] > x) {
                    j--;
                }
                if (i < j) {
                    a[i++] = a[j];
                }
                while (i < j && a[i] < x) {
                    i++;
                }
                if (i < j) {
                    a[j--] = a[i];
                }
            }
            a[i] = x;
            for(int n : a){
                System.out.print(n + " ");
            }
            System.out.println();
            if(i < k-1){
                partQuickSort(a, begin, i-1, k);
                partQuickSort(a, i+1, end, k);
            }
            if(i >= k-1){
                partQuickSort(a, begin, i-1, k);
            }
        }
    }
}
